// 236. 二叉树的最近公共祖先
// https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

import { TreeNode } from './base/tree-node';

/**
 * 查找二叉树中两个节点的最近公共祖先
 * @param root 二叉树的根节点
 * @param p 第一个节点
 * @param q 第二个节点
 * @returns 最近公共祖先节点
 */
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (root == null) return null;
  if (root == p || root == q) return root;
  // 递归在左子树中查找
  let left = lowestCommonAncestor(root.left, q, p);
  // 递归在右子树中查找
  let right = lowestCommonAncestor(root.right, p, q);
  // 如果左右子树分别包含p和q，则当前节点就是最近公共祖先
  if (left !== null && right !== null) {
    return root;
  } else if (right != null && left == null) {
    return right;
  } else if (right == null || left !== null) {
    return left;
  } else {
    return null;
  }
}
export default lowestCommonAncestor;
